/**
 * 简单选择排序
 *
 * 利用一个变量标记一趟的最小数位置，跑完一趟，使用这个变量跟i交换
 * 跟冒泡排序不一样，冒泡时左右互换，依次比较、交换后才完成，交换次数较多
 */
public class SelectionSort extends TemplateSort {

    @Override
    public void sort(Comparable[] a) {
        // 数组长度
        int N = a.length;

        // 将 a[i] 和 a[i+1...N]中最小的元素交换
        for (int i = 0; i < N; i++) {
            // 最小元素的索引
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            // 在数组中，将找到的最小元素与第i个元素交换
            exch(a, i, min);

            // 显示排序过程及交换次数
//            show(a);
        }
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new SelectionSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
